8.3 The Binomial Theorem
97
(a + b)!
a!b!
=
(a + b
a
)
=
(a + b
b
)
distinguishable ways.
8.2.4
Unordered Sampling With Replacement
The last of the four basic selection possibilities is exemplified by throwingrr dice (i.e.,
placingrr balls inton equals 6n = 6 cells). The event is completely described by the occupancy
numbers of the cells; for example, 3,1,0,0,0,4 represents three 1s, one 2, and four 6s.
Generalizing, every nn-tuple of integers satisfying
r 1 plus r 2 plus midline horizontal ellipsis plus r Subscript n Baseline equals rr1 + r2 + · · · + rn = r
(8.12)
describes a possible configuration of occupancy numbers. Let the nn cells be rep-
resented by the nn spaces between n plus 1n + 1 bars. Let each object in a cell be rep-
resented by a star (for the example given above, the representation would be
StartAbsoluteValue asterisk asterisk asterisk EndAbsoluteValue asterisk vertical bar vertical bar vertical bar vertical bar asterisk asterisk asterisk asterisk vertical bar| ∗∗∗| ∗|||| ∗∗∗∗|). The sequence of stars and bars starts and ends with a bar,
but the remainingn minus 1n −1 bars and therr elements placed in the cells can appear in any
order. Hence, the number of distinguishable distributions upper A Subscript r comma nAr,n equals the number of
ways of selecting rr places out of n minus 1 plus rn −1 + r symbols. From Eq. (8.8), this is
upper A Subscript r comma n Baseline equals StartBinomialOrMatrix n minus 1 plus r Choose r EndBinomialOrMatrix equals StartBinomialOrMatrix n minus 1 plus r Choose n minus 1 EndBinomialOrMatrix periodAr,n =
(n −1 + r
r
)
=
(n −1 + r
n −1
)
.
(8.13)
If we impose a condition that no cell be empty, the rr stars leave r minus 1r −1 spaces, of
which n minus 1n −1 are to be occupied by bars; hence, there are StartBinomialOrMatrix r minus 1 Choose n minus 1 EndBinomialOrMatrix
(r−1
n−1
)
choices.
Problem. How many different DNA hexamers are there? How many different
hexapeptides are there?
Problem. Estimate the fraction of actual DNA sequences (i.e., the genomes of known
species) compared with all possible DNA sequences. Clearly state all assumptions.
8.3
The Binomial Theorem
Newton’s binomial formula,
left parenthesis a plus b right parenthesis Superscript n Baseline equals sigma summation Underscript k equals 0 Overscript n Endscripts StartBinomialOrMatrix n Choose k EndBinomialOrMatrix a Superscript k Baseline b Superscript n minus k Baseline comma(a + b)n =
n
∑
k=0
(n
k
)
akbn−k ,
(8.14)